

		CALATORIE CU BUGET DE AUSTERITATE
	       -----------------------------------

	Un calator are de parcurs o distanta D (D<=10000), data in km. Cheltuielile datorate cala-
toriei sunt distribuite gradat in trepte astfel:

	- pentru primii l1 kilometri parcursi in fiecare zi se percepe un cost c1 per km;
	- pentru urmatorii l2 km parcursi in acea zi se percepe un cost c2 per km, s.a.m.d.

	Fiecare zi de drum presupune un cost suplimentar egal cu un numar p dat.
	Sa se determine in cate zile trebuie efectuata calatoria si cati km trebuie sa fie parcursi
in fiecare zi, astfel incat costul total al calatoriei sa fie minim. Se va furniza o solutie si
costul total corespunzator.

	Se dau la intrare:
- pe prima linie, distanta D
- pe a doua linie, numarul K de trepte (K<100)
- pe urmatoarele K linii, cate o pereche de numere li,ci (cu c(i)>c(i-1),2<=i<=k; l1+l2+..+lk<=D);
- pe ultima linie, costul suplimentar p.

	Se cer la iesire pe ecran:
- numarul n de zile stabilit
- distantele parcurse in fiecare zi
- costul total al calatoriei

	exemplu:
26		(D)
4		(K)
5 10		(l1,c1)
4 15		(l2,c2)
10 21		(l3,c3)
10 30		(l4,c4)
40		(p)

se obtine:
3		(n)
9		(prima zi)
9		(a doua zi)
8		(a treia zi)
435	

SOLUTIE:
--------

	Numarul de Km corespunzatori lungimii totale a drumului se pot distribui in mod egal in
1,2,..,d zile, eventualii Km ramasi nedistribuiti asezandu-se fie intr-o zi noua, fie intr-una din
zilele anterioare (dupa cum este mai convenabil din punctul de vedere al costului). Se retine mo-
dul optim de distribuire (numarul de zile care minimizeaza costul).

Observatie: La redistribuirea kilometrilor ramasi, dupa impartirea in mod egal a celor D kilometri
in d zile, acestia se vor adauga cate unul la cate o zi (nk_ramasi=D mod d -> nk_ramasi<d, deci se
poate distribui cate unul pe zi).